|
A Van Emde Boas tree (or Van Emde Boas priority queue; (:vɑn 'ɛmdə 'boːɑs)), also known as a vEB tree, is a tree data structure which implements an associative array with ''m''-bit integer keys. It performs all operations in O(log ''m'') time, or equivalently in O(log log ''M'') time, where M=2m is the maximum number of elements that can be stored in the tree. The ''M'' is not to be confused with the actual number of elements stored in the tree, by which the performance of other tree data-structures is often measured. The vEB tree has good space efficiency when it contains a large number of elements, as discussed below. It was invented by a team led by Dutch computer scientist in 1975.〔Peter van Emde Boas: ''Preserving order in a forest in less than logarithmic time'' (''Proceedings of the 16th Annual Symposium on Foundations of Computer Science'' 10: 75-84, 1975)〕 ==Supported operations== A vEB supports the operations of an ''ordered associative array'', which includes the usual associative array operations along with two more ''order'' operations, ''FindNext'' and ''FindPrevious'':〔Gudmund Skovbjerg Frandsen: ''(Dynamic algorithms: Course notes on van Emde Boas trees (PDF) )'' (University of Aarhus, Department of Computer Science)〕 *''Insert'': insert a key/value pair with an ''m''-bit key *''Delete'': remove the key/value pair with a given key *''Lookup'': find the value associated with a given key *''FindNext'': find the key/value pair with the smallest key at least a given ''k'' *''FindPrevious'': find the key/value pair with the largest key at most a given ''k'' A vEB tree also supports the operations ''Minimum'' and ''Maximum'', which return the minimum and maximum element stored in the tree respectively.〔 * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ''Introduction to Algorithms'', Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Chapter 20: The van Emde Boas tree, pp. 531–560.〕 These both run in ''O''(1) time, since the minimum and maximum element are stored as attributes in each tree. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Van Emde Boas tree」の詳細全文を読む スポンサード リンク
|